package datastructure.book.dp._1_pathway.all;

import org.junit.jupiter.api.Test;

import java.util.*;

public class _9_Solution {
    @Test
    public void test(){
        List<String> board = new ArrayList<>();
        board.add("E11");
        board.add("XXX");
        board.add("21S");
        System.out.println(Arrays.toString(pathsWithMaxScore(board)));
        board = new ArrayList<>();
        board.add("E1222X");
        board.add("XXXXX5");
        board.add("211674");
        board.add("312671");
        board.add("312671");
        board.add("31267S");
        System.out.println(Arrays.toString(pathsWithMaxScore(board)));
    }

    int[][] dir = new int[][]{
            {-1,0},
            {0,-1},
            {-1,-1}
    };
    char[][] chars;
    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        chars = new char[n][n];
        for (int i = 0; i < board.size(); i++) {
            String s = board.get(i);
            char[] charArray = s.toCharArray();
            chars[i] = charArray;
        }
        int[][] maxScore = new int[n][n];
        int[][] pathCnt = new int[n][n];
        pathCnt[n-1][n-1] = 1;
//        boolean[][] canReach = new boolean[n][n];
//        canReach[0][0] = true;
//        if (!dfsCanReach(canReach,n-1,n-1)){
//            return new int[]{0,0};
//        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (chars[i][j] == 'X') {
                    continue;
                }
                int rightScore = getScore(i,j+1,maxScore);
                int downScore = getScore(i+1,j,maxScore);
                int currScore = chars[i][j]-'0';
                if (chars[i][j] == 'E'){
                    currScore = 0;
                }
                if (rightScore == -1 && downScore ==-1){
                    int rightDownScore = getScore(i+1,j+1,maxScore);
                    if (rightDownScore != -1){
                        if (rightDownScore != 0 || (i+1==n-1&&j+1==n-1)){
                            maxScore[i][j] = rightDownScore+(currScore);
                            pathCnt[i][j] = pathCnt[i+1][j+1];
                        }
                    }
                }else {
                    if (rightScore == downScore){
                        if (rightScore != 0 || (i==n-1&&j+1==n-1)|| (i+1==n-1&&j==n-1)){
                            maxScore[i][j] = rightScore+currScore;
                            pathCnt[i][j] = pathCnt[i][j+1]+pathCnt[i+1][j];
                            pathCnt[i][j] %= 1000000007;
                        }
                    }else if (rightScore > downScore){
                        if (rightScore != 0 || (i==n-1&&j+1==n-1)){
                            maxScore[i][j] = rightScore+currScore;
                            pathCnt[i][j] = pathCnt[i][j+1];
                        }
                    }else {
                        if (downScore != 0 || (i+1==n-1&&j==n-1)){
                            maxScore[i][j] = downScore+currScore;
                            pathCnt[i][j] = pathCnt[i+1][j];
                        }
                    }
                }
            }
        }
        return new int[]{maxScore[0][0],pathCnt[0][0]};
    }

    private int getScore(int i, int j, int[][] maxScore) {
        if (i < 0 || i > maxScore.length - 1 || j < 0 || j > maxScore.length - 1) {
            return -1;
        }
        if (chars[i][j] == 'X'){
            return -1;
        }
        return maxScore[i][j];
    }

    private boolean dfsCanReach(boolean[][] canReach, int m, int n) {
        if (m < 0 || m > canReach.length - 1 || n < 0 || n > canReach.length - 1) {
            return false;
        }
        if (chars[m][n] == 'X') {
            return false;
        }
        if (canReach[m][n]) {
            return true;
        }
        boolean flag = false;
        for (int[] ints : dir) {
            if (dfsCanReach(canReach,m+ints[0],n+ints[1])) {
                flag = true;
                canReach[m][n] = true;
            }
        }
        return flag;
    }


}
